/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode tmp1 = head;
        ListNode tmp2 = head;
        ArrayList<Integer> ls = new ArrayList<>();
        while (tmp1 != null) {//遍历树，将节点放在list中
            ls.add(tmp1.val);
            tmp1=tmp1.next;
        }
        Collections.sort(ls);//排序
        int k=0;
        while (tmp2 != null) {
            tmp2.val = ls.get(k++);
            tmp2=tmp2.next;
        }
        return head;
    }
}